package com.wdc.queue;

import java.util.*;

/**
 * 二叉树的锯齿形层序遍历 leetcode 103
 */
@SuppressWarnings("all")
public class E01Leetcode103 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        //先实现层序遍历
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) { return  res; }


        //创建一个队列
        java.util.Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int c1 = 1; //当前层的节点数
        int c2 = 0; //下一层的节点数
        int c3  = 1; //判断奇偶
        while (!queue.isEmpty()){
            ArrayList<Integer> leve = new ArrayList<>();

            for (int i = 0; i < c1; i++ ) {
                TreeNode n = queue.poll();
                leve.add(n.val);
                if (n.left != null){
                    queue.offer(n.left);
                    c2++;
                }
                if (n.right != null){
                    queue.offer(n.right);
                    c2++;
                }
            }
            c1 = c2;
            c3++;
              /*
            这里也可以用双端队列，思路一样 只是实现的是双端队列
             */
            if (c3 % 2 != 0) Collections.reverse(leve);  //翻转链表



            res.add(leve);
        }



        return res;

    }



}
